package paixu;

/**
 * @author lj
 * @Description: 归并排序
 * @date 2020-10-30 16:11
 * @QQ 851477108
 */


public class MergeSort {
    public static int[] mergeSort(int[] arr, int l, int r){
        if (arr == null || arr.length < 2){
            return arr;
        }

        if (l == r){
            return arr;
        }
        //将数组分为两部分排序，左边[l,mid),右边[mid+1,R]
        int m = l + ((r - l) >> 1);
        mergeSort(arr,l,m); //T(n/2)
        mergeSort(arr,m + 1,r);//T(n/2)
        merge(arr, l, m, r);// O(n)
        //T(N) = 2T(n/2) + O(n)
        return arr;
    }

    private static void merge(int[] arr, int l, int m, int r) {
        //申请一个辅助数组存取左右两部分
        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        //当两部分都不越界时，通过模拟指针将两边已经排序好的数组通过一一比较
        //放到辅助数组中，谁小就放谁，直到数组越界
        while (p1<=m && p2<=r){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        //两个必有且只有一个越界
        //默认p2越界所有数值都已经放到辅助数组中
        //将p1不越界数值一一放入辅助数组中
        while (p1 <= m){
            help[i++] = arr[p1++];
        }
        //如果p1越界,放p2的值
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l+i] = help[i];
        }
    }
}
